package com.samxcode.leetcode;

/**
 * Given two numbers represented as strings, return multiplication of the numbers as a string.
 * 
 * Note: The numbers can be arbitrarily large and are non-negative.
 * 
 * 1 翻转string 
 * 2 建立数组，双层循环遍历两个string，把单位的乘积累加到数组相应的位置 
 * 3 处理进位并输出 
 * 4 注意前导零的corner case
 * 
 * @author Sam
 *
 */
public class MultiplyStrings {

    public static void main(String[] args) {
        System.out.println(multiply("98", "9"));
    }


    public static String multiply(String num1, String num2) {
        String rev1 = new StringBuilder(num1).reverse().toString();
        String rev2 = new StringBuilder(num2).reverse().toString();
        StringBuilder sb = new StringBuilder();
        int l1 = rev1.length();
        int l2 = rev2.length();
        int[] help = new int[l1 + l2];
        for (int i = 0; i < l1; i++) {
            for (int j = 0; j < l2; j++) {
                help[i + j] += (rev1.charAt(i) - '0') * (rev2.charAt(j) - '0');
            }
        }
        int digit = 0, carry = 0;
        for (int i = 0; i < help.length - 1; i++) {
            digit = help[i] % 10;
            carry = help[i] / 10;
            help[i + 1] += carry;
            sb.append(digit);
        }
        sb.append(help[help.length - 1]);
        sb.reverse();
        while (sb.charAt(0) == '0' && sb.length() > 1) {
            sb.deleteCharAt(0);
        }
        return sb.toString();
    }


    /**
     * 对于某一位i，要计算这个位上的数字，我们需要对所有能组合出这一位结果的位进行乘法，
     * 即第1位和第i位，第2位和第i-1位，... 
     * 然后累加起来，最后我们取个位上的数值，然后剩下的作为进位放到下一轮循环中
     */
    public String multiply2(String num1, String num2) {
        if (num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0)
            return "";
        if (num1.charAt(0) == '0')
            return "0";
        if (num2.charAt(0) == '0')
            return "0";
        StringBuilder res = new StringBuilder();
        int num = 0;
        for (int i = num1.length() + num2.length(); i > 0; i--) {
            for (int j = Math.min(i - 1, num1.length()); j > 0; j--) {
                if (i - j <= num2.length()) {
                    num += (int) (num1.charAt(j - 1) - '0') * (int) (num2.charAt(i - 1 - j) - '0');
                }
            }
            if (i != 1 || num > 0)
                res.append(num % 10);
            num = num / 10;
        }
        return res.reverse().toString();
    }
}
